翻訳と辞書 Words near each other ・ Expanded orgasm ・ Expanded polystyrene concrete ・ Expanded Program on Immunization ・ Expanded Program on Immunization (Philippines) ・ Expanded Psionics Handbook ・ Expanded sheet metal ・ Expanded universe ・ Expanded Universe (Heinlein) ・ Expander ・ Expander (song) ・ Expander code ・ Expander cycle ・ Expander graph ・ Expander mixing lemma ・ Expander System Sweden AB ・ Expander walk sampling ・ Expanding Anyway ・ Expanding bullet ・ Expanding Earth ・ Expanding Human ・ Expanding Man ・ Expanding Monomers ・ Expanding nozzle ・ Expanding Senses ・ Expanding toy ・ Expando ・ ExpanDrive ・ Expanse, Saskatchewan ・ Expansin ・ Expansion Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Expander walk sampling ： ウィキペディア英語版 Expander walk sampling In the mathematical discipline of graph theory, the expander walk sampling theorem states that sampling vertices in an expander graph by doing a random walk is almost as good as sampling the vertices independently from a uniform distribution. The earliest version of this theorem is due to , and the more general version is typically attributed to . ==Statement== Let $G\; =\; (V,\; E)$ be an expander graph with normalized second-largest eigenvalue $\backslash lambda$. Let $n$ denote the number of vertices in $G$. Let $f\; :\; V\; \backslash rightarrow\; (1)$ be a function on the vertices of $G$. Let $\backslash mu\; =\; E()$ denote the mean of $f$, i.e. $\backslash mu\; =\; \backslash frac\; \backslash sum\_\; f(v)$. Then, if we let $Y\_0,\; Y\_1,\; \backslash ldots,\; Y\_k$ denote the vertices encountered in a $k$-step random walk on $G$ starting at a random vertex $Y\_0$, we have the following for all $\backslash gamma\; >\; 0$: :$\backslash Pr\backslash left(\backslash sum\_^k\; f(Y\_i)\; -\; \backslash mu\; >\; \backslash gamma\backslash right)\; \backslash leq\; e^.$ Here the $\backslash Omega$ hides an absolute constant $\backslash geq\; 1/10$. An identical bound holds in the other direction: : 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Expander walk sampling」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.